{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ModCalculation:\n",
    "    def __init__(self, mod=0):\n",
    "        self.mod = mod\n",
    "\n",
    "    def get_mod(self, a):\n",
    "        return a % self.mod if self.mod else a\n",
    "\n",
    "    def _add(self, a, b):\n",
    "        return (a + b) % self.mod if self.mod else a + b\n",
    "\n",
    "    def add(self, *args):\n",
    "        s = 0\n",
    "        for i in args:\n",
    "            s = self._add(s, i)\n",
    "        return s\n",
    "\n",
    "    def sum(self, iterable):\n",
    "        return self.add(*iterable)\n",
    "\n",
    "    def mul_(self, a, b):\n",
    "        return (a * b) % self.mod if self.mod else a * b\n",
    "\n",
    "    def mul(self, *args):\n",
    "        res = 1\n",
    "        for i in args:\n",
    "            res = self.mul_(res, i)\n",
    "        return res\n",
    "\n",
    "    def power(self, a, n):\n",
    "        res = 1\n",
    "        while n:\n",
    "            res = self.mul(res, a)\n",
    "        return res\n",
    "\n",
    "    def quick_power(self, a, n):\n",
    "        res = 1\n",
    "\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                res = self.mul(res, a)\n",
    "\n",
    "            a = self.mul(a, a)\n",
    "            n >>= 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "class LinearSpace(ModCalculation):\n",
    "    def __init__(self, dim, mod=0):\n",
    "        super().__init__(mod)\n",
    "        self.dim = dim\n",
    "\n",
    "        self.E = [[0] * dim for _ in range(dim)]\n",
    "        for i in range(dim):\n",
    "            self.E[i][i] = 1\n",
    "\n",
    "    def axb(self, a, b):\n",
    "        return self.sum(self.mul(i, j) for i, j in zip(a, b))\n",
    "\n",
    "    def axA(self, a, A):\n",
    "        return [self.sum(self.mul(a[i], A[i][j]) for i in range(self.dim)) for j in range(self.dim)]\n",
    "\n",
    "    def AxB(self, A, B):\n",
    "        return [self.axA(a, B) for a in A]\n",
    "\n",
    "    def quick_power(self, A, n):\n",
    "        res = self.E\n",
    "\n",
    "        B = A\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                res = self.AxB(res, B)\n",
    "\n",
    "            B = self.AxB(B, B)\n",
    "            n >>= 1\n",
    "\n",
    "        return res"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.9.12"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "3a176caed2e623e3a36a87b094ae4f1cc68623d3a88a2d36a2ea84f7c5d7277a"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
